A. Technical Field
The present invention relates generally to networking and the communication of data over a network, and more particularly, to transparent on-line encoding and decoding of a continuous stream of network communications data.
B. Background of the Invention
Due to the exponential growth of network communications traffic, the amount of bandwidth available for transmission of data is often exceeded by the amount of data to be transmitted. This high demand for bandwidth results in network congestion and communication delays. One way to address this problem of limited bandwidth availability is to encode the transmitted data in a more efficient format. This encoding process reduces the size of the data and can therefore be referred to as data compression. The encoded or compressed data contains the same information as the original data but requires fewer bits to be stored or transmitted. The encoding or compression process is referred to as a loss-less process if the original data can be exactly recovered from the encoded or compressed data.
The Open Systems Interconnection (OSI) Reference Model is a widely used model describing the flow of data across a network. The OSI model has seven layers. Each of the seven layers communicates with the layer below it through a specific interface and to its peer layer on a different system on the network through a specific protocol. The combination of all networking layers is often referred to as the networking stack.
The lowest layer (layer 1) of the OSI model is the physical layer. It addresses the transmission of bits of information across a physical link. The next layer (layer 2) is the data link layer, which addresses transmission of blocks of data across a link provided by the physical layer. The data link layer addresses issues such as sharing media with multiple systems connected to a network (e.g., ethernet), addressing of systems that are directly connected to each other, and computing checksums of the transmitted blocks of data. The next layer (layer 3) is the network layer, which allows any two systems on the network to talk to each other even if they are not directly connected with a physical link. Hence, the network layer performs route calculations based on a destination address and accordingly routes packets of information across a network. The next layer (layer 4) is the transport layer which provides a flow of data between two systems. The transport layer operates on an entire flow of data between two systems rather than on individual packets of data. TCP (Transmission Control Protocol) is one of the protocols of the transport layer. TCP provides reliable transport of data between two systems by ensuring that all information transmitted from one system to another is actually received and is received in the order that it was transmitted. The TCP protocols provide this functionality by dealing with errors such as lost and reordered packets. The next three layers are the session layer (layer 5), presentation layer (layer 6) and the application layer (layer 7). The application layer (layer 7) is the highest layer of the OSI model and is usually the interface that is provided to system users. For example, an email message is generated at the application level by a user and is processed in turn by each of the seven networking layers to be finally transmitted on the network. A more detailed description of the OSI model is set forth in Tanenbaum, Computer Networks, 2d Ed. (1989) which is incorporated by reference herein in its entirety.
The communication between two systems can be broadly classified into two categories: connectionless and connection-oriented. Connectionless communication occurs when the data is presented as an independent package including address information, and the network delivers each package independent of all other packages being exchanged on the network. Connection-oriented communication occurs when two systems first execute a set-up procedure to create a real or virtual connection and then exchange multiple pieces of data over the same connection.
The packet based TCP/IP (Transmission Control Protocol/Internet Protocol) protocols are two of the most widely known protocols of the Internet. IP is a network layer protocol that defines a set of standards for the addressing and routing of packets across a connectionless network. TCP is a connection-oriented transport layer protocol that defines a means for ensuring reliable transport of information across a network. Note that IP is considered connectionless since each packet is treated independently. TCP on the other hand is connection-oriented since it involves first setting up a TCP connection between the two systems after which all pieces of data utilize the same virtual link. Note that a connection-oriented service, such as TCP, can be implemented over a connectionless layer, such as IP.
Encoding or compression of network communications data can be performed at different layers of the networking stack. Traditionally, data is encoded at the application layer (layer 7). For instance, images can be encoded in a variety of formats, such as the Graphics Interchange Format (gif) or Joint Photographic Experts Group format (jpeg). These encoding formats reduce the space required for storage or transmission of the image. Hence, at the application level the server can encode all of its images in the “gif” format before transmission to the client. Each image received by the client is then decoded at the application level to generate the original viewable image. This form of application layer encoding or compression is usually performed off-line on single objects prior to transmission. Application layer encoding is not performed in an on-line fashion to a continuous communication stream consisting of multiple objects. Hence, off-line application level encoders are based only on intra-object information (i.e., information from a single object) rather than inter-object information (i.e., information from all of the different objects transmitted from one or more servers to one or more clients).
Since the transport level of the OSI model is a connection-oriented service, on-line encoding techniques applied at this level will effectively be encoding a connection-oriented link. Hence the encoding will only be performed on the data that is transmitted within a single connection or single flow. In a client-server architecture, since each connection is between the server and a single client, an independent encoding process will have to be executed for every client. Similarly, there will need to exist an independent decoder for every client that receives data from the server. Thus on-line encoding of a connection-oriented link can only be effectively performed when the number of connections (i.e., sessions or flows) is small, i.e., the server only communicates with a single or a few clients. In addition, encoding data within a single connection will not be as effective as encoding all of the connections together in the same process because the encoding process will only be able detect repetitions that exist within the same session. For instance there may be several data patterns or objects that are transmitted only once in each independent layer 4 session (e.g., a TCP session). In this example, if the encoder examines each session independently it will not detect any repetitions since each object or pattern is transmitted only once per session. On the other hand, if the encoder examines all of the data traffic across all of the sessions, it will detect many more repetitions and hence it will encode the traffic more efficiently.
Other implementations of encoding or compression in the networking domain have been based encoding traffic at the connection-less layer 3. These layer 3 encoding techniques have been based only on intra-packet encoding. Hence, these systems encode each packet or datagram independently based only on the information within the current packet. They cannot, therefore, detect repetitions of entire packets or repetitions that exist across multiple packets. These intra-packet layer 3 encoding techniques therefore miss many repetitions and do not yield a high degree of data reduction.
Accordingly it is desirable to provide improved efficiency of data transmission and bandwidth utilization. Current encoding schemes are limited by the amount of data that they examine and hence they can only detect a small fraction of the total number of repetitions that exist in all of the network communications traffic. For instance, encoding schemes that encode each packet independently can only detect repetitions that exist within the same packet. Similarly, encoding schemes that treat each session independently can only detect repetitions that exist within the same session. Also, encoding schemes that are based on specific applications or data types can only detect repetitions that exist within the data of that specific type. In all of these cases, repetitions that occur across packets or across sessions or across data types are never detected. Hence current encoding schemes are not efficient and yield only a relatively small degree of data reduction.